In local area networks of the centralized bus type, e.g. datakit, the buffers used for queuing data on the port boards of such systems are subject to congestion or overflow during periods of high traffic on the network.
A problem exists with respect to the provision of port buffers that are cost effective and also minimize the possibility of buffer overflow. Obviously, the overflow problem would not exist if buffers of unlimited size could be used. This however, is not economically feasible because of the cost of large buffers. Instead, it is necessary to use buffers of moderate size and to adopt system operating procedures that provide for the efficient use of the provided buffers.
A first such procedure that could be used ignores the actual buffer size and assumes that the buffer is of unlimited capacity. All virtual circuit calls are accepted by the system even though buffer overflow takes place. This procedure relies on the error correction capabilities of the end-to-end protocol used by the sending and receiving stations to correct any data that is lost or mutilated due to buffer overflow. A typical error recovery technique requires the sending station to retransmit any packets that are lost or mutilated. This procedure has the undesirable consequence of further increasing traffic in a system that is already congested. This can cause a further loss of data and even still more retransmission and, in turn, more congestion.
Another procedure that could be used logically allocates a fixed amount of buffer space to each virtual call regardless of the actual buffer space required by the call. The system then accepts no further calls that require the use of a fully allocated buffer. This procedure assumes that each call uses all of its allocated buffer space. Thus, new calls are sometimes not served in accordance with this procedure even though free buffer space actually exists. This technique is disadvantageous since each call does not require the same amount of buffer space and some calls do not use all of their buffer allocation.
Other flow control mechanisms are known that avoid buffer overflow, but such mechanisms require that the data transmission protocol be terminated in the packet switch port or at each network node. Such an arrangement is disclosed in U.S. Pat. No. 4,475,192, issued Oct. 2, 1984 to J. P. Fernow and R. P. Levy. Fernow discloses a multi node system in which each node terminates the protocol and independently provides for flow control between it and adjacent nodes. This arrangement is satisfactory for large wide area networks which can afford the costs and complexity of such an arrangement. However, the Fernow et al system is not suitable for small local area networks where speed and economy are paramount. In particular, such systems are not suitable for use in a centralized bus packet switching systems of the type comprising the subject matter of the present invention.
Thus, a problem still exists in local area networks regarding the provision of an efficient congestion control mechanism for preventing buffer overflow.